'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-06 07:03:26
'''
'''
5454. 统计全 1 子矩形
给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

 

示例 1：

输入：mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
示例 2：

输入：mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
示例 3：

输入：mat = [[1,1,1,1,1,1]]
输出：21
示例 4：

输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
输出：5
'''


'''
tips:dp作为中间被用到，还是蛮有意思的。dp[i, j]状态记录以(i, j)为右下角的这一行，i的个数。
这样dp[i, j] = dp[i, j-1] + 1 if mat[i, j] == 1 else 0
再遍历i, j，以(i, j)为右下角，向上遍历k in (i, 0), 这样，直接取dp[k, j]即为该行最多有多少个
连续的1，将这个值处理下即可。
'''
from typing import List

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        import sys
        dp = [[0]*len(mat[0]) for _ in mat] #定义状态
        re = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]:
                    dp[i][j] = dp[i][j-1] + 1
                mmin = sys.maxsize
                for k in range(i, -1, -1):
                    mmin = min(mmin, dp[k][j])
                    re += mmin
                    if not mmin:
                        break

        return re
if __name__ == "__main__":
    solution = Solution()
    mat = [[1,0,1],[0,1,0],[1,0,1]]
    print(solution.numSubmat(mat))